/*
 * algorithm.c
 * adapted from the gnu-c++ library
 *  Created on: Sep 8, 2008
 *      Author: lindenb
 */
#include <string.h>
#include "util/algorithm.h"
#include "util/debug.h"
#define distance( first, last, item_size) (((BytePtr)last-(BytePtr)first)/item_size)


#define COMPARE(fun,a,b) (fun!=NULL?fun(a,b):memcmp(a,b,item_size))



int lower_bound(
		Ptr base,
		size_t nmembers,
		size_t item_size,
		int(*compare)(const Ptr, const Ptr),
		Ptr key
		)
	{
	BytePtr __first = (BytePtr)base;
	BytePtr __last = ((BytePtr)__first)+(nmembers*item_size);

	size_t __len =  distance(__first, __last,item_size);
	size_t __half;
	BytePtr __middle;

    while (__len > 0)
		{
		 __half = __len/2;
		 __middle = __first +(__half*item_size);


		 if (COMPARE(compare,__middle,key) < 0)
			{
			__first = __middle;
			__first+= item_size;
			 __len = __len - __half - 1;
			}
		  else
			{
			__len = __half;
			}
		}

    return distance(base,__first,item_size);
	}

int upper_bound(
		BytePtr base,
		size_t nmembers,
		size_t item_size,
		int(*compare)(const void *, const void *),
		BytePtr key
		)
	{
	BytePtr __first = (BytePtr)base;
	BytePtr __last = ((BytePtr)__first)+(nmembers*item_size);

	size_t __len =  distance(__first, __last,item_size);
	size_t __half;
	BytePtr __middle;

    while (__len > 0)
	{
     __half = __len/2;
     __middle = __first +(__half*item_size);
	  if (COMPARE(compare,key, __middle)<0)
	    __len = __half;
	  else
	    {
	      __first = __middle;
	      __first+= item_size;
	      __len = __len - __half - 1;
	    }
	}
    return  distance(base,__first,item_size);
	}

